#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
using namespace std;

void prtArr(bool *a, int n) {
  printf("--- bool[%d] ---\n", n);
  for (int i = 0; i < n; i++) printf("%d", a[i]);
  printf("\n");
}

void prtMat(bool *a, int n, int m) {
  printf("--- bool[%d,%d] ---\n", n, m);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) printf("%d", a[i * n + j]);
    printf("\n");
  }
}

void prtIntArr(int *a, int n) {
  printf("--- int[%d] ---\n", n);
  for (int i = 0; i < n; i++) printf("%d ", a[i]);
  printf("\n");
}

void prtIntMat(int *a, int n, int m) {
  printf("--- int[%d,%d] ---\n", n, m);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) printf("%3d ", a[i * m + j]);
    printf("\n");
  }
}
void prt(vector<int> v) {
  int n = v.size();
  printf("--- vector(%d) ---\n", n);
  for (int i = 0; i < n; i++) printf("%d ", v[i]);
  printf("\n");
}
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};